package com.wuyou.mid;


import java.util.*;

/**
 * 146. LRU 缓存
 */
public class LRUCache {

    public static class LRUCacheNode {
        int key, val;
        LRUCacheNode pre, next;

        public LRUCacheNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    Map<Integer, LRUCacheNode> map;
    LRUCacheNode head, tail;
    private int capacity;
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = this.tail = new LRUCacheNode(-1, -1);
        this.size = 0;
    }

    public int get(int key) {
        LRUCacheNode node = this.getNode(key);
        return node == null ? -1 : node.val;
    }

    private LRUCacheNode getNode(int key){
        LRUCacheNode node = map.get(key);
        if (node != null){
            if (node.next == null){
                this.tail = node.pre;
            }
            else {
                node.next.pre = node.pre;
            }
            node.pre.next = node.next;

            node.next = head.next;
            if (head.next != null){
                head.next.pre = node;
            }
            head.next = node;
            node.pre = head;
            if (node.next == null){
                this.tail = node;
            }
        }
        return node;
    }

    public void put(int key, int value) {
        LRUCacheNode node = this.getNode(key);
        if (node != null){
            node.val = value;
            return;
        }
        node = new LRUCacheNode(value, key);
        if (this.size >= this.capacity){
            LRUCacheNode pre = this.tail.pre;
            this.tail.pre = null;
            pre.next = null;
            map.remove(this.tail.key);
            this.tail = pre;
        }
        else {
            this.size++;
        }
        node.pre = this.head;
        node.next = this.head.next;
        if (this.head.next != null){
            this.head.next.pre = node;
        }
        this.head.next = node;
        if (node.next == null){
            this.tail = node;
        }
        map.put(key, node);
    }

}
